package 动态规划.另类的;

import org.junit.Test;
import sort.对数器;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/1/8 21:37
 */
public class leetcode152最大乘积子数组 {


    /*
     方法一：  dp 有点 绕
        1.理解一下空间压缩，如果 f(i) 只依赖与 f(i + 1) 的话,那就没必要使用数组,直接 用 有限 几个变量就行了!
        2. 理解 f(i) 的含义

     方法二: 观察思考(数学规律)!

     */
    /*
     这个 暴力递归还是 有点意思的！
     首先 理解 f（i） 的含义
     f(i) 表示的是 以 i 开头的 连续子数组 的 最大值 max ,以及 最小值 min
     发现没 f(i) 表示的 值 有多个 ,那么 返回的记过  用一个  数组 来接 不就行了!
     int [] =  f(i)

     ---
     还可以进行 拓展,无论  f(i) 表示的 含义 有几个 ,都可以 用 f[x] 来表示
     x 是 f(i) 可能要记录的情况 数, 这里 有两个结果 要 记录
     1. max
     2. min
     */

    public int [] recursion(int index,int []nums){
        /*
          下面两种basecase
          各有各的 使用场合
          这一点要十分 注意 一下就行 了!
         */


        // 这是 另外 一种basecase
        if(index == nums.length - 1){
            return new int []{nums[index],nums[index]};
        }

        // 这是 一种 basecase
        if(index == nums.length){
            return new int[]{1,1};
        }
        /*
        由于存在负数，那么会导致最大的变最小的，最小的变最大的。
        因此还需要维护当前最小值imin
         */
        // temp[0] 表示 以 i 开头的 最小值, tmep[1] 表示 以 i 开头的最大值
        int temp [] = recursion(index + 1,nums);
        int min = Math.min(Math.min(temp[0] * nums[index],temp[1] * nums[index]),nums[index]);
        int max = Math.max(Math.max(temp[0] * nums[index],temp[1] * nums[index]),nums[index]);
        return  new int []{min,max};
    }

    /*
    改成 dp
    首先 要注意上面的 暴力递归 只能算出 以  index 开头的 最值
    所以 我们 在 dp 的 时候 要 统计 最大值 是 在 那个 index开头的结果
    ---
    这个 dp 其实 有点意思的
    本来只有一个 变化的参数 ,dp数组是 一维的
   但是 考虑 到 结果的特殊性,这里 得是 二维 数组
   dp[i][0] 表示 以 i 开头得 最小值
   dp[i][1] 表示 以 i开头得最大值
     */
    public static int dp(int []nums){
        int len = nums.length;
        int dp[][] = new int [len][2];
        int ans = dp[len - 1][0] = dp[len - 1][1] = nums[len - 1];
        for(int i = len - 2;i >= 0;i--){
            dp[i][0] = Math.min(Math.min(dp[i + 1][0] * nums[i],dp[i + 1][1] * nums[i]),nums[i]);
            dp[i][1] = Math.max(Math.max(dp[i + 1][0] * nums[i],dp[i + 1][1] * nums[i]),nums[i]);
            ans = Math.max(ans,dp[i][1]);
        }
        return ans;
    }

    /*
     从这个 dp 得 状态 转移 依赖关系可以看出
     f (i) 只依赖 与 f(i + 1) 那么 就没要 使用  缓存表来记录 了
     直接使用有限几个变量就 行了!
    这个 时间 上, 和空间上 都有小小的加速!
     */
    public static int dpSaveMem(int []nums){
        int len = nums.length;
//        int dp[][] = new int [len][2];
        int max,min;
        int ans = max = min = nums[len - 1];
        for(int i = len - 2;i >= 0;i--){
            /*
             这里 注意一下 ,要用一个 变量temp 记录 一下 min
             否则 max 在 使用 min ,使用 得 就是 当前层 的 min
             但是 max 需要的是  i + 1 的min
             这一点要看懂的!
             */
            int temp = min;
            min = Math.min(Math.min(min * nums[i],max * nums[i]),nums[i]);
            max = Math.max(Math.max(temp * nums[i],max * nums[i]),nums[i]);
            ans = Math.max(ans,max);
        }
        return ans;
    }
    /*
       这种 分开 判断的  思路 要比  上面 写的 那种复杂 好理解  一些;
       但是本质上都 是一样, 理解 原理 是什么的话, 其实都还好!
          for (int i = 1; i < len; i++) {
            if (nums[i] >= 0) {
                dp[i][1] = Math.max(nums[i], dp[i - 1][1] * nums[i]);
                dp[i][0] = Math.min(nums[i], dp[i - 1][0] * nums[i]);
            } else {
                dp[i][1] = Math.max(nums[i], dp[i - 1][0] * nums[i]);
                dp[i][0] = Math.min(nums[i], dp[i - 1][1] * nums[i]);
            }
        }

     */



    /*
     写个 暴力 ＋ 前缀积的方式
     来写一下 ，看下能不能行

     - 对数器 测了一下， 感觉 是没有任何问题的
     只是， 有 0 存在的 话， 前缀积 就有点扯淡了！
     */

    public int function(int nums[]){
        // 这里的 ans  一开始 初始化 是 0， 但是 这样是错误的， 因为 该题 本身 0 就具有特殊性，也不能够 初始化 int 最小值， 也是不对的！
        int ans = nums[nums.length - 1],len = nums.length , preMuti[] = new int[len + 1];
        preMuti[0] = 1;
        for(int i = 0;i < len;i++){
            preMuti[i + 1] = preMuti[i] *  nums[i];
        }
        for(int i = 0;i < len ;i++){
            for(int j = i;j < len;j++){
                ans = Math.max(ans,preMuti[j + 1] / preMuti[i]);
            }
        }
        return ans;
    }



    @Test
    public void test(){
        for(int i = 0;i < 10;i++){
            int[] ints = 对数器.ramdomArray(20, 30, -1, false);
            int function = function(ints);
            int i1 = dpSaveMem(ints);
            System.out.println(function + " ------   " + i1);
        }

    }




}
